#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "windows.h"
//洗牌算法
void swap(int arr[],int p,int s)
{
	int tmp = arr[s];
	arr[s] = arr[p];
	arr[p] = tmp;
	return;
}
void knuth2(int arr[],int n)
{
	
	srand((unsigned )time(NULL));
	for (int i = n - 1  ; i >= 1 ; i--) {
		int x = rand()%(i + 1);
		swap(arr,i,x);
	}
}
void RandomArr(int arr[],int n)
{
	for (int i = 0; i < n; i++) {
		arr[i] = i;
	}
	knuth2(arr,n);
}
//获取随机值10-99
void createHarr(int Harr[],int arr[],int n)
{
	knuth2(arr,600);
	for (int i = 0; i < n; ++i) {
		Harr[i] = arr[i];
	}
}

// 生成有序数组
void OrderArr(int arr[],int n)
{
	int i;
	for(i = 0; i < n; i++) {
		arr[i] = i + 1;
	}
	return;
}
double Bubble(int arr[],int n)
{
	
	LARGE_INTEGER num;
	LONGLONG start, end,freq;
	QueryPerformanceFrequency(&num);
	freq = num.QuadPart;
	QueryPerformanceFrequency(&num);
	start = num.QuadPart;
	
	//todo
	int i,j;
	for(i = 0;i < n;i++) {
		int flag = 0;
		for(j = 0; j <= n - i - 1 ; j++) {
			if(arr[j] > arr[j + 1]) {
				flag = 1;
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
		if(flag == 0) {
			break;
		}
	}
	
	QueryPerformanceFrequency(&num);
	end = num.QuadPart;
	//printf(" %8.2f ms ",(end - start) * 1000.0/freq);
	return (end - start) * 1000.0/freq;
}
//直接插入排序
double DirInsertSort(int arr[],int n)
{
	LARGE_INTEGER num;
	LONGLONG start, end,freq;
	QueryPerformanceFrequency(&num);
	freq = num.QuadPart;
	QueryPerformanceFrequency(&num);
	start = num.QuadPart;
	int i,j,temp;
	for(i = 1; i < n; i++) {
		if (arr[i - 1] > arr[i])
		{
			// 获取需要插入的数据
			temp = arr[i];
			// 依次后移，查找插入位置
			for ( j = i - 1; j >= 0 && arr[j] > temp; j--)
			{
				arr[j + 1] = arr[j];
			}
			// 完成插入
			arr[j + 1] = temp;
		}
		
	}
	QueryPerformanceFrequency(&num);
	end = num.QuadPart;
	//printf(" %8.2f ms ",(end - start) * 1000.0/freq);
	return (end - start) * 1000.0/freq;
}
//快速选择排序
double quickSort(int arr[], int low, int high)
{
	LARGE_INTEGER num;
	LONGLONG start, end,freq;
	QueryPerformanceFrequency(&num);
	freq = num.QuadPart;
	QueryPerformanceFrequency(&num);
	start = num.QuadPart;
	
	if (low > high)
	{
		return -1;
	}
	int i = low, j = high, temp = arr[i];//获取左右和基准数
	while (i < j)
	{
		while (temp < arr[j] && i < j)
		{
			j--;
		}
		if (i < j)
		{
			arr[i++] = arr[j];
		}
		while (temp>arr[i] && i < j)
		{
			
			i++;
		}
		if (i < j)
		{
			arr[j--] = arr[i];
		}
	}
	arr[i] = temp;
	
	quickSort(arr, low, i - 1);//左边
	quickSort(arr, i + 1, high);//右边
	
	QueryPerformanceFrequency(&num);
	end = num.QuadPart;
	//printf(" %8.2f ms ",(end - start) * 1000.0/freq);
	return (end - start) * 1000.0/freq;
}

//堆排序
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
	
	int rc,j;
	rc=a[s];
	for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
	{
		if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
		if(rc>a[j]) break;
		a[s]=a[j];s=j;
	}
	a[s]=rc;//插入
}
double HeapSort(int a[],int n)
{
	LARGE_INTEGER num;
	LONGLONG start, end,freq;
	QueryPerformanceFrequency(&num);
	freq = num.QuadPart;
	QueryPerformanceFrequency(&num);
	start = num.QuadPart;
	int temp, i, j;
	for (i = n / 2; i > 0; i--)//通过循环初始化顶堆
	{
		HeapAdjust(a, i, n);
	}
	for (i = n; i > 0; i--) {
		temp = a[1];
		a[1] = a[i];
		a[i] = temp;//将堆顶记录与未排序的最后一个记录交换
		HeapAdjust(a, 1, i - 1);//重新调整为顶堆
	}
	QueryPerformanceFrequency(&num);
	end = num.QuadPart;
	//printf(" %8.2f ms ",(end - start) * 1000.0/freq);
	return (end - start) * 1000.0/freq;
}
void test1() {
	int arr[60000];
	OrderArr(arr,60000);
	double Bub = Bubble(arr,60000);
	double Insert = DirInsertSort(arr,60000);
	//double fast = quickSort(arr,0,59999);
	double heap = HeapSort(arr,60000);
	printf("======= 排序算法对比  (将 60000 个无重复有序/乱序数据按升序排序) ======\n");
	printf("\n");
	printf("--------------------第01轮对比 初始有序序列排序性能 --------------------\n");
	printf("----排序算法----  - 排序耗时 - ---------随机展示5个排序后的连续数据---------\n");
	printf("【时间复杂度 O（n^2)】\n");
	printf("  冒泡排序          %.2f     ",Bub);
	for (int i = 37456; i < 37461; ++i) {
		printf("%d  ",arr[i]);
	}
	printf("\n");
	printf("  直接插入排序       %.2f     ",Insert);
	for (int i = 31000; i < 31005; ++i) {
		printf("%d  ",arr[i]);
	}
	printf("\n");
	printf("【时间复杂度 O（nlogn)】\n");
	printf("  快速排序          %.2f     ",heap);
	for (int i = 17456; i < 17461; ++i) {
		printf("%d  ",arr[i]);
	}
	printf("\n");
	printf("  堆排序            %.2f     ",heap);
	for (int i = 42000; i < 42005; ++i) {
		printf("%d  ",arr[i]);
	}
	printf("\n");
	
}


int main() {
	
	//    //double fast = quickSort(arr,0,59999);
	//    double heap = HeapSort(arr,60000);
	//    printf("%f  ",heap);
	test1();
	//int arr[60000];
	//int arr1[10] = {2,6,8,9,1,2,3,7,5,6};
	//    int arr[20];
	//    double a =  Bubble(arr,60000);
	//    printf("%8.2f ms ",a);
	//DirInsertSort(arr1,10);
	//double a = quickSort(arr1,0,59999);
	//HeapSort(arr1,9);
	//print1(arr1);
	//OrderArr(arr,20);
	//    RandomArr(arr,20);
	//    for (int i = 0; i < 10; ++i) {
	//        printf("%d ",arr1[i]);
	//    }
	//printf("%f",a);
	return 0;
}

